# -*- coding: utf-8 -*-

"""1641. 统计字典序元音字符串的数目
给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

示例 1：
输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]

示例 2：
输入：n = 2
输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后

示例 3：
输入：n = 33
输出：66045

提示：
1 <= n <= 50"""

class Solution:
    """观察规律，n增加1层，
        末尾为 a 的量取决与上一次末尾为 (a) 的量；
        末尾为 e 的量取决与上一次末尾为 (a + e) 的量；
        末尾为 i 的量取决与上一次末尾为 (a + e + i) 的量；
        末尾为 o 的量取决与上一次末尾为 (a + e + i + o) 的量；
        末尾为 u 的量取决与上一次末尾为 (a + e + i + o + u) 的量；
        
        这道题应该还能用数学归纳法来得出数学上的结果，计算效率更高，我还得不出这个函数。"""
    def countVowelStrings(self, n: int) -> int:
        a, e, i, o, u = 1, 1, 1, 1, 1
        # print('a:%s, e:%s, i:%s, o:%s, u:%s' % (a, e, i, o, u))
        x = 1
        while x < n:
            a = a        # a    注释为上层的字符串结尾为各元音的量
            e = a + e    # a + e    注释为上层的字符串结尾为各元音的量
            i = e + i    # a + e + i    注释为上层的字符串结尾为各元音的量
            o = i + o    # a + e + i + o    注释为上层的字符串结尾为各元音的量
            u = o + u    # a + e + i + o + u    注释为上层的字符串结尾为各元音的量
            # print('a:%s, e:%s, i:%s, o:%s, u:%s' % (a, e, i, o, u))
            x += 1
        return a + e + i + o + u

if __name__ == '__main__':
    print(Solution().countVowelStrings(1))
    print(Solution().countVowelStrings(2))
    print(Solution().countVowelStrings(33))
